/**
 * 279. 完全平方数
 * https://leetcode-cn.com/problems/perfect-squares/
 */

// /**
//  * @param {number} n
//  * @return {number}
//  */
// function numSquares(n) {
//   const cache = new Array(n + 1).fill(false);
//   const last = Math.floor(Math.sqrt(n));
//   const squares = new Array(last);
//   const half = n / 2;
//   for (let i = 1; i <= last; i += 1) {
//     const num = i * i;
//     cache[num] = true;
//     squares[i - 1] = num;
//   }
//   const dp = new Array(n + 1).fill(0);
//   for (let i = 1; i <= n; i += 1) {
//     if (cache[i]) {
//       dp[i] = 1;
//       continue;
//     }
//     let minCount = Infinity;
//     for (let j = 0; squares[j] <= half; j += 1) {
//       const count = dp[squares[j]] + dp[i - squares[j]];
//       if (count < minCount) {
//         minCount = count;
//       }
//     }
//     dp[i] = minCount;
//   }
//   return dp[n];
// }

/**
 * @param {number} n
 * @return {number}
 */
function numSquares(n) {
  const dp = new Array(n + 1).fill(0);
  let min;
  let count;
  for (let i = 1; i <= n; i += 1) {
    const end = Math.floor(Math.sqrt(i));
    min = Infinity;
    for (let j = 1; j <= end; j += 1) {
      count = dp[i - j * j];
      if (count < min) {
        min = count;
      }
    }
    dp[i] = min + 1;
  }
  return dp[n];
}

console.log(numSquares(12) === 3);
console.log(numSquares(13) === 2);
